1. Field of the Invention
This invention relates to a method and apparatus for extracting contour lines of a binary image stored in the sequence of raster scanning.
2. Description of the Related Art
Heretofore, when, for example, forming an outline font from a binary dot pattern, contour lines of a binary image character pattern are extracted and stored in the form of vector information, and an outline font of a character is formed from the stored information. Such extraction of contour lines by a binary image is started from finding the start point for tracking a contour line of the binary image. When the start point for tracking has been found, a contour of the image is sequentially tracked from the start point, and tracking is continued while successively providing tracked contour points with marks indicating the completion of tracking. One contour point string (a contour line) is obtained when a loop is formed as a result of tracking. By repeating such a procedure, all the contour lines of the image can be extracted.
FIG. 2 shows an example of the procedure of a well-known contour tracking operation using 8 adjacent pixels. In FIG. 2, a binary image pattern 201 includes a blank portion 202 in an inner portion thereof. A case of extracting contour lines of this pattern will be explained. In FIG. 2, one section represents one dot (pixel (picture element)).
(1) The binary image pattern 201 is subjected to raster scanning from a reference point (0, 0) of the picture surface.
(2) If the raster scanning hits a point (for example, dot 203) not having a mark indicating the completion of tracking, contour tracking of the dot pattern is started from that point P0. If such a point P0 is absent in the entire picture surface, the procedure is terminated.
(3) Tracking is started in the sequence shown in FIG. 3 in the directions of 8 pixels adjacent to the start point P0. A point where a pixel is first met (dot 204 in the case of FIG. 2) is made to be the next contour point P1. If no adjacent point is present, the point is made to be an isolated point, and the process returns to procedure (2).
(4) After marking a contour point Pi in the above-described manner, the next contour point Pi+1 is extracted from among 8 pixels adjacent to the point Pi, as shown in FIG. 4. In searching if any dot is present in the counterclockwise direction around the point Pi (dot 402) starting from a point 401 which has just been marked, a point where a pixel is first met is made to be the next contour point Pi+1.
(5) Subsequently, contour points are successively obtained by repeating the above-described procedure (4).
If Pn+1=P1 and Pn=P0, the contour line string of one region is formed by points P0, P1, . . . , Pnxe2x88x921, and the process proceeds to procedure (6).
(6) The process returns to procedure (2) in order to obtain the contour line string of another image region.
Thus, contour tracking is completed. In FIGS. 3 and 4, point  represents a target point, and point ⊙ (401) represents a point which has just been marked. Numerals shown in FIGS. 3 and 4 indicate the sequence of searching the presence of a pixel (dot).
In the above-described conventional approach, however, since tracking along a contour line is performed after determining the start point for contour tracking, processing of extracting the contour line must be started after receiving the entire image in a memory. Accordingly, the needed capacity of the memory is increased, causing, for example, an increase in the production cost and processing time.
Furthermore, since the start point for the next contour is detected by another raster scanning after extracting one contour point string, pixels which have already been searched are searched again, causing an increase in the amount of calculation of image data, and a decrease in processing speed.
In the above-described conventional approach, a contour is tracked along a center of a pixel (dot), not along sides of a pixel (dot) as shown in FIG. 2. Hence, if a dot pattern having a width of one dot is tracked, the width of the detected contour line is reduced to zero width rather than a one dot width.
The present invention has been made in consideration of the above-described problems.
It is an object of the present invention to provide a contour extraction apparatus and method which can extract all contours contained in an image with one raster scanning by performing raster scanning of the image, extracting a contour while moving the position of a target pixel, determining the position of the target pixel and the presence of black points in pixels adjacent to the target pixel, extracting candidates for the start points and the end points of vectors on a contour vector string in accordance with the state of the black points, and determining the start point and the end point connected to these candidates.
It is a further object of the present invention to provide a contour extraction apparatus comprising hold means (e.g., latches) for holding states of target pixels and pixels adjacent to the respective target pixels in image data, detection means for taking out the target pixel in the sequence of raster scanning, and detecting a pixel arranging vector in the horizontal direction and in the vertical direction according to the state of the target pixel and pixels adjacent to the target pixel, determination means for determining a state of connection between the pixel arrangement vectors, and extraction means for extracting a contour of the image data according to the state of connection between the pixel arrangement vectors determined by the determination means.
It is a still further object of the present invention to provide a contour extraction method comprising the steps of selecting a point in the image data according to a state of a target pixel and pixels adjacent to the target pixel a point constituting a contour line and determining a direction of connection of points of the contour line according to a state of the adjacent pixels, determining a state of connection between the point constituting the contour line and another point of the contour line, and setting the position of the target pixel in image data in the sequence of raster scanning and extracting a contour point by executing the above-described steps according to the state of adjacent pixels for every target pixel.
It is still another object of the present invention to provide a contour extraction method which holds states of target pixels and pixels adjacent to the respective target pixels in image data, takes out the target pixel in the sequence of raster scanning, detects a pixel arranging vector in the horizontal direction and in the vertical direction according to the state of the target pixel and pixels adjacent to the target pixel, determines a state of connection between the pixel arranging vectors, and extracts a contour of the image data according to the determined state of connection state between the pixel arranging vectors.